import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //构造二叉树的节点：
    //
    //public TreeNode root;//将来这个引用指向的就是根节点。
    //我现在并没有创建好二叉树
    //现在手动的方式取创建，来穷举一个二叉树
    //A-B-C-D-E-F
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        //先手动创建一下这个东西，
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        //手动去把他们连起来
        //此时我们用A作为根节点，直接干掉预先定义的根节点。

        return A;//返回根节点，函数返回类型改变一下
    }

    //接下来我们要对这棵树进行遍历
    //递归本来就是大问题化解为小问题
    //当小问题解决后，大问题也就解决了
    public void prevOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");//这一步骤是对根的访问，也就是，进行的操作。
        //咱们这里仅仅只是打印了，没有进行其他的操作。
        prevOrder(root.left);
        prevOrder(root.right);
    }

    //java你是真的闲，我没使用这个函数你都报错
    //
    public List<TreeNode> prevOrder3(TreeNode root) {
        List<TreeNode> ret = new ArrayList<>();
        if (root == null) return ret;

        ret.add(root);
        //咱们这里仅仅只是打印了，没有进行其他的操作。
        List<TreeNode> leftTree = prevOrder3(root.left);
        ret.addAll(leftTree);
        List<TreeNode> rightTree = prevOrder3(root.right);
        ret.addAll(rightTree);
        return ret;
        //画一个图你就理解了。最后所有的值都存进来了，这种更加的优雅

        //合理利用所有的返回值，最中装到最外层的这个ret链表中
    }

    List<TreeNode> ret = new ArrayList<>();

    public List<TreeNode> prevOrder2(TreeNode root) {
        if (root == null) {
            return ret;
            //合理的利用返回值
        }
        //咱们这里仅仅只是打印了，没有进行其他的操作。
        //用返回值将他们来弄起来
        ret.add(root);
        prevOrder2(root.left);
        prevOrder2(root.right);
        return ret;//这里没有合理的利用返回值

    }

    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //咱们这里仅仅只是打印了，没有进行其他的操作。
        prevOrder(root.left);
        System.out.print(root.val + " ");//这一步骤是对根的访问，也就是，进行的操作。
        //order是次序的意思，
        prevOrder(root.right);

    }

    //    public List<Character> inOrder2(TreeNode root){
//        List<Character> ret= new ArrayList<>();
//        if(root==null) return ret;
//
//        //咱们这里仅仅只是打印了，没有进行其他的操作。
//        List<TreeNode> leftTree=inOrder2(root.left);
//        ret.addAll(leftTree);
//        ret.add(root.val);//这里报错是因为类型不一样
//        List<TreeNode> rightTree=inOrder2(root.right);
//        ret.addAll(rightTree);
//        return ret;
//        //画一个图你就理解了。最后所有的值都存进来了，这种更加的优雅
//        //合理利用所有的返回值，最中装到最外层的这个ret链表中
//    }
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //咱们这里仅仅只是打印了，没有进行其他的操作。
        prevOrder(root.left);
        //order是次序的意思，
        prevOrder(root.right);
        System.out.print(root.val + " ");//这一步骤是对根的访问，也就是，进行的操作。
    }

    //    public List<TreeNode> postOrder2(TreeNode root){
//        List<TreeNode> ret= new ArrayList<>();
//        if(root==null) return ret;
//
//        //咱们这里仅仅只是打印了，没有进行其他的操作。
//        List<TreeNode> leftTree=prevOrder3(root.left);
//        ret.addAll(leftTree);
//        List<TreeNode> rightTree=prevOrder3(root.right);
//        ret.addAll(rightTree);
//        ret.add(root.val);
//        return ret;
//        //画一个图你就理解了。最后所有的值都存进来了，这种更加的优雅
//        //合理利用所有的返回值，最中装到最外层的这个ret链表中
//    }
    //
    public int size = 0;

    public void nodeSize(TreeNode root) {
        //以前序遍历、中序遍历、后序遍历的时候，每个树都会遍历到
        //遍历这个树的时候，
        if (root == null)
            return;
        size++;
        nodeSize(root.left);
        nodeSize(root.right);
        return;
        //这个时候调用这个方法不用通过返回值来得到个数，而是直接去访问成员变量size
        //你调用这个函数，目的是为了更新二叉树的节点值，更新后，然后去获得size值
        //遍历思路--是一种很简单的思路
        //能不能不用遍历思路呢？
        //子问题的思路：
        //左子树节点个数+1+右子树节点个数

    }

    public int nodeSize2(TreeNode root) {
        if (root == null)
            return 0;
        return nodeSize2(root.left) + nodeSize2(root.right) + 1;
        //这个代码太优雅了
        //最后确实全部转化为0和1相加
        //每一个树都可以使用左子树节点个数加右子树节点个数+1

    }

    public int leafSize = 0;
    public void getLeafSize(TreeNode root){
        if(root==null) return;
        if(root.left==null&&root.right==null){//写的时候不要昏头昏脑，这里的左右都为null，就是找的度为0的
            leafSize++;
        }
        getLeafSize(root.left);
        getLeafSize(root.right);
    }
    //继续去使用子问题的思路
    public int getLeafSize2(TreeNode root){
        if(root==null) return 0;//这种情况是只有一个根节点
        //return nodeSize2(root.left) + nodeSize2(root.right);
        if (root.right==null&&root.left==null){
            return 1;
        }
        getLeafSize2(root.left);
        getLeafSize2(root.right);
        return getLeafSize2(root.left) + getLeafSize2(root.right);

    }
    //不写遍历
    //写子问题
    ////也就是去总结递归公式。
    //得到最大值的逻辑
    //真的6
    //你要做过很多的题

//    public int getLevelNodeCount(TreeNode root){
//
//    }
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        return getHeight(root.left)>getHeight(root.right) ? getHeight(root.left)+1:getHeight(root.right)+1;
        //三目表达式真的是优雅，但是有没有哪里有问题呢？？
        //这样写，就会把数字给算两次，会有点问题，会超出时间限制--OJ，
        //死循环
        //递归条件错误
        //规定一秒，你使用了两秒
        //所以此处看起来优雅，但是会重复很多的计算，本来递归运算量就大，这样运算量更大了，超过OJ的时间限制
        
    }
    public boolean find(TreeNode root,char key){
        if(root==null){
            return false;
        }
        if(root.val==key){
            return true;
        }
        boolean leftVal=find(root.left,key);
        if(leftVal==true){
            return true;
        }
        boolean rightVal=find(root.right,key);
        if(rightVal==true){
            return true;
        }

        return false;//在这个树里面根本找不到。
        //
    }
    //检查两颗树是否相同
    //结构上；相同，节点值相同
    //需要同时满足
    //核心技术卷，那个时候没有报班
    //一到家就很难执行
    //任何时间阶段都是有借口的
    //返回值不是必须的
    //方法没有被使用
    //idea都会
    //他们已经开始实习了，快点，要在寒假之前就要学完，尽量为实习做准备，
    //根节点相同，左子树相同，右子树相同---结构相同
    //在判断结构相同的同时，取判断值是否一致
    //两种跳出条件，一个是结构不一样
    //一个是对应结构的对应值不一样
    //采用前序遍历的方式是最佳的
    //因为首先就访问根节点了
    //时间复杂度拿出来，阁下有应当如何应对呢？
    //计算时间复杂度，需要结合算法的思想
    //判断一个树是都是一棵树的子树
    //等于根节点的左子树或者节点的右子树
    //两个完全一样是子树吗？？？
    //是的，特殊情况可以直接去判断相同。
    //用刚刚写过的
    //左子树等于这个树
    //他的柞树是不是相同，他的右树是不是相同
    //反复的判断相同
    //不相同取判断左子树相同吗？

    public boolean isSameTree(TreeNode p,TreeNode q){
        if(p==null&&q==null){
            return true;
        }
        if(p==null&&q!=null||q==null&&p!=null){
            return false;
        }
        if(p.val==q.val){
            return true;
        }
        return false;
    }
    //二叉树的反转：
    //根节点不变，左子树和右子树方砖
    //然后对左子树和右子树进行相同的操作
    //所以最开始的时候，它给的那个二叉树应该是一个对称的二叉树
    //二叉树，一会要自己实现了一下
    //
    //判断一个树是不是高度平衡的二叉树
    //先判断是不是空
    //左右两边的值来相减
    //不能只通过一个节点下面平衡来判断
    //需要判断每一个节点都是高度平衡的
    //只有每一个树都是高度平衡的，
    //求树的高度
    //对每个节点都去求高度，
    //只要有一个不平衡的，
    //重复的也太离谱了吧？？
    //根本没有必要啊，求高度的时候判断平衡，不平衡直接就
    //不代表它不对，只是复杂度很高，
    //用一个标志，来代表我们在判断此节点是否平衡的过程中找到了不平衡的
    //这个时间只是参考，哈哈哈
    //只能一次打破一个函数的栈帧
    //所以想法没有办法实现了
    //只能用一些这样的方法
    //还有更好的办法吗？
    //这就是字节跳动问过的题
    //你要见过的够多
    //不要把

    //把他干掉，每写一遍，看的越来越少，
    //把他删掉，自己在写
    //反复去写那些题目，确保自己真的可以手写出来
    //轴对称二叉树
    //判断一个树是不是轴对称
    public List<List<TreeNode>> levelOrder (TreeNode root){
        List<List<TreeNode>> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){

        }
        //
        //
        //确定根
        //确定左树和右树
        //你的代码顺序也是跟随遍历的顺序的
        //
    }
}